package com.taldh.algorithm.treenode;

import com.taldh.algorithm.base.TreeNode;
import org.junit.Assert;
import org.junit.Test;

public class IsBalanced {

    public boolean isBalanced(TreeNode root) {
        int minDepth = minDepth(root);
        int maxDepth = maxDepth(root);
        return (maxDepth - minDepth) < 2;
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);


        return Math.min(leftDepth+1, rightDepth + 1);
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = maxDepth(root.left);
        int rigthDepth = maxDepth(root.right);

        return leftDepth > rigthDepth ? (leftDepth+1) : (rigthDepth+1);

    }

    @Test
    public void test() {
        Assert.assertFalse(isBalanced(new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3)))));
    }

}
